{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Sub-Folders from the Filesystem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #trie #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #字典树 #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeSubfolders"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除子文件夹"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你是一位系统管理员，手里有一份文件夹列表 <code>folder</code>，你的任务是要删除该列表中的所有 <strong>子文件夹</strong>，并以 <strong>任意顺序</strong> 返回剩下的文件夹。</p>\n",
    "\n",
    "<p>如果文件夹&nbsp;<code>folder[i]</code>&nbsp;位于另一个文件夹&nbsp;<code>folder[j]</code>&nbsp;下，那么&nbsp;<code>folder[i]</code>&nbsp;就是&nbsp;<code>folder[j]</code>&nbsp;的 <strong>子文件夹</strong> 。</p>\n",
    "\n",
    "<p>文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：<font color=\"#c7254e\"><font face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"font-size:12.6px\"><span style=\"background-color:#f9f2f4\">'/'</span></span></font></font>&nbsp;后跟一个或者多个小写英文字母。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"/leetcode\"</code>&nbsp;和&nbsp;<code>\"/leetcode/problems\"</code>&nbsp;都是有效的路径，而空字符串和&nbsp;<code>\"/\"</code>&nbsp;不是。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>folder = [\"/a\",\"/a/b\",\"/c/d\",\"/c/d/e\",\"/c/f\"]\n",
    "<strong>输出：</strong>[\"/a\",\"/c/d\",\"/c/f\"]\n",
    "<strong>解释：</strong>\"/a/b\" 是 \"/a\" 的子文件夹，而 \"/c/d/e\" 是 \"/c/d\" 的子文件夹。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>folder = [\"/a\",\"/a/b/c\",\"/a/b/d\"]\n",
    "<strong>输出：</strong>[\"/a\"]\n",
    "<strong>解释：</strong>文件夹 \"/a/b/c\" 和 \"/a/b/d\" 都会被删除，因为它们都是 \"/a\" 的子文件夹。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> folder = [\"/a/b/c\",\"/a/b/ca\",\"/a/b/d\"]\n",
    "<strong>输出:</strong> [\"/a/b/c\",\"/a/b/ca\",\"/a/b/d\"]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= folder.length &lt;= 4 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>2 &lt;= folder[i].length &lt;= 100</code></li>\n",
    "\t<li><code>folder[i]</code>&nbsp;只包含小写字母和 <code>'/'</code></li>\n",
    "\t<li><code>folder[i]</code>&nbsp;总是以字符 <code>'/'</code>&nbsp;起始</li>\n",
    "\t<li><code>folder</code>&nbsp;每个元素都是 <strong>唯一</strong> 的</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-sub-folders-from-the-filesystem](https://leetcode.cn/problems/remove-sub-folders-from-the-filesystem/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-sub-folders-from-the-filesystem](https://leetcode.cn/problems/remove-sub-folders-from-the-filesystem/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"/a\",\"/a/b\",\"/c/d\",\"/c/d/e\",\"/c/f\"]', '[\"/a\",\"/a/b/c\",\"/a/b/d\"]', '[\"/a/b/c\",\"/a/b/ca\",\"/a/b/d\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        folder.sort()\n",
    "        res.append(folder[0])\n",
    "        for i in range(1, len(folder)):\n",
    "            if not((pre := len(res[-1])) < len(folder[i]) and res[-1] == folder[i][:pre] and folder[i][pre] == '/'):\n",
    "                res.append(folder[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val, is_leaf):\n",
    "        self.val = val\n",
    "        self.childs = {}\n",
    "        self.is_leaf = is_leaf\n",
    "\n",
    "    def add_child(self, tree_node):\n",
    "        self.childs[tree_node.val] = tree_node\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def has_parent(self, tree, names):\n",
    "        if not names:\n",
    "            return False\n",
    "\n",
    "        if names[0] not in tree.childs:\n",
    "            return tree.is_leaf\n",
    "        return self.has_parent(tree.childs[names[0]], names[1:])\n",
    "\n",
    "    def add_child(self, dummy_head, names):\n",
    "        cur_node = dummy_head\n",
    "        for index, name in enumerate(names):\n",
    "            node = TreeNode(name, index == len(names) - 1)\n",
    "            cur_node.add_child(node)\n",
    "            cur_node = node\n",
    "\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        dummy_head = TreeNode(-1, False)\n",
    "        res = []\n",
    "        for f in folder:\n",
    "            names = f[1:].split(\"/\")\n",
    "            if not self.has_parent(dummy_head, names):\n",
    "                res.append(f)\n",
    "                self.add_child(dummy_head, names)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        ans = [folder[0]]\n",
    "        for i in range(1, len(folder)):\n",
    "            if not((pre := len(ans[-1])) < len(folder[i]) and ans[-1] == folder[i][:pre] and folder[i][pre] == \"/\"):\n",
    "                ans.append(folder[i])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        res, t = [], '//'\n",
    "        for f in sorted(folder):\n",
    "            if not f.startswith(t):\n",
    "                res.append(f)\n",
    "                t = f + '/'\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        res = [folder[0]]\n",
    "        for f in folder[1:]:\n",
    "            m = len(res[-1])\n",
    "            n = len(f)\n",
    "            if m >= n or not(res[-1] == f[:m] and f[m] == '/'):\n",
    "                res.append(f)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        ans = [folder[0]]\n",
    "        for f in folder[1:]:\n",
    "            if f.startswith(ans[-1]) and f[len(ans[-1])] == '/':\n",
    "                continue\n",
    "            ans.append(f)\n",
    "        return ans\n",
    "\n",
    "                    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort(key=lambda x: len(x))\n",
    "        temp = set()\n",
    "        for f in folder:\n",
    "            flag = False\n",
    "            p = \"\"\n",
    "            for i in f[1:].split(\"/\"):\n",
    "                p += \"/\" + i\n",
    "                if p in temp:\n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag:\n",
    "                temp.add(f)\n",
    "        return list(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        s=sorted(folder,key = lambda x:(len(x)))\n",
    "        ans=[]\n",
    "        d=[]\n",
    "        for i in s:\n",
    "            p=''\n",
    "            flag=True\n",
    "            for j in i:\n",
    "                if j=='/':\n",
    "                    if p in d:\n",
    "                        flag=False\n",
    "                        break\n",
    "                p+=j\n",
    "            if flag:\n",
    "                ans.append(i)\n",
    "                d.append(i)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        res = [folder[0]]\n",
    "        for i in range(1,len(folder)):\n",
    "            if res[-1]+'/' == folder[i][:len(res[-1])+1]:\n",
    "                continue\n",
    "            else:\n",
    "                res.append(folder[i])\n",
    "        return res\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        # 首先，对文件夹路径进行排序，以确保相似的文件夹路径都在一起。\n",
    "        folder.sort()\n",
    "        \n",
    "        # 创建一个用于存储结果的字符串列表 ans，并将第一个文件夹路径添加到其中。\n",
    "        ans = [folder[0]]\n",
    "        \n",
    "        # 遍历文件夹路径列表，从第二个文件夹路径开始。\n",
    "        for f in folder[1:]:\n",
    "            # 获取前一个文件夹路径的长度\n",
    "            m, n = len(ans[-1]), len(f)\n",
    "            \n",
    "            # 使用条件语句检查当前文件夹路径是否为前一个文件夹路径的子文件夹\n",
    "            # 条件的目的是检查当前文件夹路径是否以前一个文件夹路径为前缀，且在前一个文件夹路径的末尾是一个斜杠'/'\n",
    "            if m >= n or not (ans[-1] == f[:m] and f[m] == '/'):\n",
    "                # 如果不是子文件夹，则将当前文件夹路径添加到结果中\n",
    "                ans.append(f)\n",
    "        \n",
    "        # 返回不包含子文件夹的文件夹路径列表\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort() \n",
    "        remain = []\n",
    "        for p in folder:\n",
    "            flag = True\n",
    "            rm_list = []\n",
    "            for r in remain:\n",
    "                if p.startswith(r):\n",
    "                    if p[len(r)] == '/':\n",
    "                        flag = False\n",
    "                        break\n",
    "\n",
    "                # if r.startswith(p):\n",
    "                #     if r[len(p)] == '/':\n",
    "                #         rm_list.append(r)\n",
    "            if flag:\n",
    "                remain.append(p)\n",
    "            # for i in rm_list:\n",
    "            #     remain.remove(i)\n",
    "        return remain\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        folder.sort()\n",
    "        for index,fold in enumerate(folder):\n",
    "            if index == 0: ans.append(folder[index])\n",
    "            elif len(fold) > len(ans[-1]) and fold[0:len(ans[-1])] == ans[-1] and fold[len(ans[-1])] == '/':\n",
    "                continue\n",
    "            else: ans.append(folder[index])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        ans = [folder[0]]\n",
    "        for f in folder[1:]:\n",
    "            m, n = len(ans[-1]), len(f)\n",
    "            if m >= n or not (ans[-1] == f[:m] and f[m] == '/'):\n",
    "                ans.append(f)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        res = [folder[0]]\n",
    "        for i in range(1, len(folder)):\n",
    "            if not ((pre := len(res[-1])) < len(folder[i]) and res[-1] == folder[i][:pre] and folder[i][pre] == '/'):\n",
    "                res.append(folder[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        ans = [folder[0]]\n",
    "        for f in folder[1:]:\n",
    "            if f.startswith(ans[-1]) and f[len(ans[-1])] == '/':\n",
    "                continue\n",
    "            ans.append(f)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def removeSubfolders(self, folder):\n",
    "        folder.sort()\n",
    "        res = [folder[0]]\n",
    "        for i in range(1, len(folder)):\n",
    "            if not ((pre := len(res[-1])) < len(folder[i]) and res[-1] == folder[i][:pre] and folder[i][pre] == \"/\"):\n",
    "                res.append(folder[i])\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrefix(self, s1:List[str], s2:List[str]):\n",
    "        l1=len(s1)\n",
    "        l2=len(s2)\n",
    "        if l1>l2:\n",
    "            return False\n",
    "        for i in range(l1):\n",
    "            if s1[i]!=s2[i]:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def removeSubfolders1(self, folder: List[str]) -> List[str]:\n",
    "        folderlist=[]\n",
    "        for f in folder:\n",
    "            folderlist.append(f.split(\"/\")[1:])\n",
    "        folderlist.sort(key=lambda x:len(x))\n",
    "        print(folderlist)\n",
    "        n=len(folder)\n",
    "        for i in range(n-1):\n",
    "            j=i+1\n",
    "            while j<len(folderlist):\n",
    "                if self.isPrefix(folderlist[i], folderlist[j]):\n",
    "                    folderlist.pop(j)\n",
    "                else:\n",
    "                    j+=1\n",
    "        res=[\"/\"+\"/\".join(f) for f in folderlist]\n",
    "        return res\n",
    "\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        res=[folder[0]]\n",
    "        for f in folder[1:]:\n",
    "            m,n=len(res[-1]), len(f)\n",
    "            if m>=n or not(res[-1]==f[:m] and f[m]==\"/\"):\n",
    "                res.append(f)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        s=sorted(folder,key = lambda x:(len(x)))\n",
    "        ans=[]\n",
    "        d=[]\n",
    "        for i in s:\n",
    "            p=''\n",
    "            flag=True\n",
    "            for j in i:\n",
    "                if j=='/':\n",
    "                    if p in d:\n",
    "                        flag=False\n",
    "                        break\n",
    "                p+=j\n",
    "            if p in d:\n",
    "                flag=False\n",
    "            if flag:\n",
    "                ans.append(i)\n",
    "                d.append(i)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        p = set(folder)\n",
    "        res = []\n",
    "        # print(p)              \n",
    "        for f in folder:\n",
    "            xs = f.split('/')\n",
    "            find = False\n",
    "            for i in range(1, len(xs)):\n",
    "                curp = '/'.join(xs[:i])\n",
    "                # print(curp)\n",
    "                if curp in p:\n",
    "                    find = True\n",
    "                    break\n",
    "            if not find:\n",
    "                res.append(f)                    \n",
    "        return res                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        # root = set()\n",
    "        folder.sort()\n",
    "        if len(folder) == 1:\n",
    "            return folder[0]\n",
    "        n = len(folder)\n",
    "        # root.add(folder[0])\n",
    "        root = [folder[0]]\n",
    "        for i in range(1, n):\n",
    "            if folder[i].startswith(root[-1]+'/'):\n",
    "                continue\n",
    "            else:\n",
    "                root.append(folder[i])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "## 常规方法\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        ans = [folder[0]]\n",
    "        for i in range(1, len(folder)):\n",
    "            if not ((pre := len(ans[-1])) < len(folder[i]) and ans[-1] == folder[i][:pre] and folder[i][pre] == \"/\"):\n",
    "                ans.append(folder[i])\n",
    "        return ans\n",
    "\n",
    "## 字典树+深度优先搜索\n",
    "# class Trees():\n",
    "#     def __init__(self):\n",
    "#         self.children = dict()\n",
    "#         self.ref = -1 \n",
    "# class Solution:\n",
    "#     def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "#         root = Trees()\n",
    "#         for i , paths in enumerate(folder):\n",
    "#             path = paths.strip().split('/')\n",
    "#             cur = root\n",
    "#             for node in path:\n",
    "#                 if node not in cur.children:\n",
    "#                     cur.children[node] = Trees()\n",
    "#                 cur = cur.children[node]\n",
    "#             cur.ref = i\n",
    "#         ans = []\n",
    "#         def dfs(node):\n",
    "#             if node.ref != -1:\n",
    "#                 ans.append(folder[node.ref])\n",
    "#                 return\n",
    "#             for children in node.children.values():\n",
    "#                 dfs(children)\n",
    "#         dfs(root)\n",
    "#         return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        results = []\n",
    "        for f in folder:\n",
    "            if not results: \n",
    "                results.append(f)\n",
    "                continue\n",
    "            if not f.startswith(results[-1]+\"/\"): results.append(f)\n",
    "        return results\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        # 删除，可以定义新的返回结果\n",
    "        # 遍历 截取当前字符串的前半部分，如果不等 加入结果 \n",
    "        res = []\n",
    "        previous = ' '\n",
    "        for f in sorted(folder):\n",
    "            length = len(previous)\n",
    "            if f[:length] != previous:\n",
    "                res.append(f)\n",
    "                previous = f + '/'\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        l, r, lenf, ans = 0, 0, len(folder), []\n",
    "        while r < lenf:\n",
    "            ans.append(folder[l])\n",
    "            s1, r = folder[l] + '/', l + 1\n",
    "            while r < lenf and folder[r].startswith(s1): r += 1\n",
    "            if r < lenf: l = r\n",
    "            else: return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        ans = [folder[0]]\n",
    "        for f in folder[1:]:\n",
    "            m, n = len(ans[-1]), len(f)\n",
    "            if m > n or not (ans[-1] == f[:m] and f[m] == '/'):\n",
    "                ans.append(f)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder):\n",
    "        folder.sort()\n",
    "        result = []\n",
    "        result.append(folder[0])\n",
    "\n",
    "        for i in range(1, len(folder)):\n",
    "            if not folder[i].startswith(result[-1] + '/'):\n",
    "                result.append(folder[i])\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, f: List[str]) -> List[str]:\n",
    "        f.sort()\n",
    "        i, j, n, res = 0, 1, len(f), []\n",
    "        while j < n:\n",
    "            if len(f[j]) > len(f[i]) and f[j][:len(f[i])] == f[i] and f[j][len(f[i])] == '/':\n",
    "                pass\n",
    "            else:\n",
    "                res.append(f[i])\n",
    "                i = j\n",
    "            j += 1\n",
    "        else:\n",
    "            res.append(f[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        ans = [folder[0]]\n",
    "        n = len(folder)\n",
    "        for i in range(1, n):\n",
    "            l = len(ans[-1])\n",
    "            if not (l < len(folder[i]) and ans[-1] == folder[i][:l] and folder[i][l] == \"/\"):\n",
    "                ans.append(folder[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        ans = []\n",
    "        for i in range(len(folder)):\n",
    "            if folder[i] == '' or folder[i] == '/': continue\n",
    "            if not ans: ans.append(folder[i])\n",
    "            elif len(folder[i]) > len(ans[-1]) and folder[i][:len(ans[-1])] == ans[-1] and folder[i][len(ans[-1])] == '/':\n",
    "                continue\n",
    "            else:\n",
    "                ans.append(folder[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 使用API判断路径前缀是否已加入答案路径数组中\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        folder.sort(key=lambda x: len(x))\n",
    "\n",
    "        for s in folder:\n",
    "            suc = False\n",
    "            for pre in ans:\n",
    "                if len(pre) == len(s):\n",
    "                    break\n",
    "                if s.startswith(pre) and s[len(pre)] == '/':\n",
    "                    suc = True\n",
    "                    break\n",
    "            if not suc:\n",
    "                ans.append(s)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        # 首先，对文件夹路径进行排序，以确保相似的文件夹路径都在一起。\n",
    "        folder.sort()\n",
    "        \n",
    "        # 创建一个用于存储结果的字符串列表 ans，并将第一个文件夹路径添加到其中。\n",
    "        ans = [folder[0]]\n",
    "        \n",
    "        # 遍历文件夹路径列表，从第二个文件夹路径开始。\n",
    "        for f in folder[1:]:\n",
    "            # 获取前一个文件夹路径的长度\n",
    "            m, n = len(ans[-1]), len(f)\n",
    "            \n",
    "            # 使用条件语句检查当前文件夹路径是否为前一个文件夹路径的子文件夹\n",
    "            # 条件的目的是检查当前文件夹路径是否以前一个文件夹路径为前缀，且在前一个文件夹路径的末尾是一个斜杠'/'\n",
    "            if m >= n or not (ans[-1] == f[:m] and f[m] == '/'):\n",
    "                # 如果不是子文件夹，则将当前文件夹路径添加到结果中\n",
    "                ans.append(f)\n",
    "        \n",
    "        # 返回不包含子文件夹的文件夹路径列表\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "      res = []\n",
    "      t = '//'\n",
    "      for f in sorted(folder):\n",
    "        if not f.startswith(t):\n",
    "          res.append(f)\n",
    "          t = f + '/'\n",
    "      return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        n = len(folder)\n",
    "        stack = [folder[0]]\n",
    "        for i in range(1, n):\n",
    "            pre = stack[-1].split(\"/\")\n",
    "            cur = folder[i].split(\"/\")\n",
    "            if len(pre) != len(cur) or pre == cur:\n",
    "                now = list(x for x in cur if x not in pre)\n",
    "                if pre + now == cur or pre == cur:\n",
    "                    continue\n",
    "            stack.append(folder[i])\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        res, t = [], '//'\n",
    "        for f in sorted(folder):\n",
    "            if not f.startswith(t):\n",
    "                res.append(f)\n",
    "                t = f + '/'\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        ans = [folder[0]]\n",
    "        for f in folder[1:]:\n",
    "            m, n = len(ans[-1]), len(f)\n",
    "            if m >= n or not (ans[-1] == f[:m] and f[m] == '/'):\n",
    "                ans.append(f)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        tag = set()\n",
    "        folder.sort(key=lambda e: len(e), reverse=False)\n",
    "        for i in folder:\n",
    "            cur = i.split('/')\n",
    "            loc = 0\n",
    "            end = len(cur)\n",
    "            while loc < end:\n",
    "                if '/'.join(cur[:loc + 1]) in tag:\n",
    "                    loc += 1\n",
    "                    break\n",
    "                loc += 1\n",
    "            tag.add('/'.join(cur[:loc]))\n",
    "        return list(tag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        ans = [folder[0]]\n",
    "        for f in folder[1:]:\n",
    "            m, n = len(ans[-1]), len(f)\n",
    "            if not (m < n and ans[-1] == f[:m] and f[m] == '/'):\n",
    "                ans.append(f)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "\n",
    "        n = len(folder)\n",
    "        res = [folder[0]]\n",
    "        for i in range(1, n):\n",
    "            m, n = len(res[-1]), len(folder[i])\n",
    "            if m >= n or not (res[-1] == folder[i][:m] and folder[i][m] == '/'):\n",
    "                res.append(folder[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        ans = [folder[0]]\n",
    "        for i in range(1, len(folder)):\n",
    "            pre = len(ans[-1])\n",
    "            if not (pre < len(folder[i]) and ans[-1] == folder[i][:pre] and folder[i][pre] == \"/\"):\n",
    "                ans.append(folder[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        ans = [folder[0] + \"/\"]\n",
    "        for i in range(1, len(folder)):\n",
    "            if not folder[i].startswith(ans[-1]):\n",
    "                ans.append(folder[i] + \"/\")\n",
    "        return [v[:-1] for v in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        ans = [folder[0]]\n",
    "        for f in folder[1:]:\n",
    "            m, n = len(ans[-1]), len(f)\n",
    "            if m >= n or not (ans[-1] == f[:m] and f[m] == '/'):\n",
    "                ans.append(f)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        # 删除，可以定义新的返回结果\n",
    "        # 遍历 截取当前字符串的前半部分，如果不等 加入结果 \n",
    "        res = []\n",
    "        previous = ' '\n",
    "        for f in sorted(folder):\n",
    "            length = len(previous)\n",
    "            if f[:length] != previous:\n",
    "                res.append(f)\n",
    "                previous = f + '/'\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        vis = set()\n",
    "        for f in folder:\n",
    "            cur = ''\n",
    "            for ch in f:\n",
    "                if ch == '/':\n",
    "                    if cur in vis:\n",
    "                        break\n",
    "                cur += ch\n",
    "            else:\n",
    "                vis.add(f)\n",
    "        \n",
    "        return list(vis)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        vist = set()\n",
    "        folder.sort(key=lambda x: len(x))\n",
    "        remove_arr = []\n",
    "        for i in folder:\n",
    "            cur = i.split('/')\n",
    "            cur.pop(0)\n",
    "            n = len(cur)\n",
    "            left = 0\n",
    "            res = False\n",
    "            while left < n:\n",
    "                arr = cur[:left+1]\n",
    "                file = '/' + '/'.join(arr)\n",
    "                if file in vist:\n",
    "                    res = True\n",
    "                    break\n",
    "                left += 1\n",
    "            if res:\n",
    "                remove_arr.append(i)\n",
    "            else:\n",
    "                vist.add(i)\n",
    "\n",
    "        return list(vist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "\n",
    "        folder.sort()\n",
    "\n",
    "        res = [folder[0]]\n",
    "\n",
    "        for i in range(1, len(folder)):\n",
    "\n",
    "            pre = len(res[-1])\n",
    "            if not (pre < len(folder[i]) and res[-1] == folder[i][:pre] and folder[i][pre] == \"/\"):\n",
    "                res.append(folder[i])\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort()\n",
    "        ans = [folder[0]]\n",
    "        for f in folder[1:]:\n",
    "            m, n = len(ans[-1]), len(f)\n",
    "            if m >= n or not (ans[-1] == f[:m] and f[m] == '/'):\n",
    "                ans.append(f)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        # folder.sort()\n",
    "        # l, r, lenf, ans = 0, 0, len(folder), []\n",
    "        # while r < lenf:\n",
    "        #     ans.append(folder[l])\n",
    "        #     s1, r = folder[l] + '/', l + 1\n",
    "        #     while r < lenf and folder[r].startswith(s1):\n",
    "        #         r += 1\n",
    "        #     if r < lenf:\n",
    "        #         l = r\n",
    "        #     else:\n",
    "        #         return ans\n",
    "\n",
    "        folder.sort()\n",
    "        l, r, lenf, ans = 0, 0, len(folder), []\n",
    "        while r < lenf:\n",
    "            ans.append(folder[l])\n",
    "            s1, r = folder[l] + '/', l + 1\n",
    "            while r < lenf and folder[r].startswith(s1):\n",
    "                r += 1\n",
    "            if r < lenf:\n",
    "                l = r \n",
    "            else:\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "\n",
    "        folder.sort()\n",
    "\n",
    "        res = [folder[0]]\n",
    "\n",
    "        for i in range(1, len(folder)):\n",
    "\n",
    "            pre = len(res[-1])\n",
    "            if not (pre < len(folder[i]) and res[-1] == folder[i][:pre] and folder[i][pre] == \"/\"):\n",
    "                res.append(folder[i])\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folders = sorted(folder)\n",
    "        dd = folders[0]\n",
    "        ff = dd.split('/')\n",
    "        print(ff)\n",
    "        cc = len(ff)\n",
    "        ss = [dd]\n",
    "        for i in folders[1:]:\n",
    "            gg = i.split('/')\n",
    "            if ff != gg[:cc]:\n",
    "                cc = len(gg)\n",
    "                ff = gg\n",
    "                ss.append(i)\n",
    "        print(ss)\n",
    "        return ss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node(object):\n",
    "    def __init__(self, word):\n",
    "        self.word = word\n",
    "        self.is_fold = False\n",
    "        self.children = {}\n",
    "\n",
    "    def generate_child(self, w_list, idx):\n",
    "        if idx >= len(w_list) or self.is_fold:\n",
    "            return\n",
    "        if w_list[idx] not in self.children:\n",
    "            node = Node(f\"{self.word}/{w_list[idx]}\")\n",
    "            self.children[w_list[idx]] = node\n",
    "        if idx == len(w_list) - 1:\n",
    "            self.children[w_list[idx]].is_fold = True\n",
    "            return\n",
    "        self.children[w_list[idx]].generate_child(w_list, idx + 1)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort(key=lambda f: len(f))\n",
    "        root_node = Node(\"\")\n",
    "        mp = {}\n",
    "        self.res = []\n",
    "        for f in folder:\n",
    "            w_list = f[1:].split('/')\n",
    "            root_node.generate_child(w_list, 0)\n",
    "        self.get_res(root_node)\n",
    "        return self.res\n",
    "\n",
    "    def get_res(self, node):\n",
    "        if node.is_fold:\n",
    "            self.res.append(node.word)\n",
    "            return\n",
    "        for child_node in node.children.values():\n",
    "            self.get_res(child_node)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 字典树\n",
    "\n",
    "CHARSET = 26\n",
    "\n",
    "\n",
    "class node:\n",
    "    def __init__ (self):\n",
    "        self.nexts = [None] * (CHARSET + 1)\n",
    "        self.isEnd = False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "\n",
    "        root = node()\n",
    "\n",
    "        def add(s: str) -> bool:\n",
    "            cur = root\n",
    "            for i, c in enumerate(s):\n",
    "                idx = ord(c) - ord('a')\n",
    "                if idx < 0:\n",
    "                    idx = CHARSET\n",
    "                if cur.nexts[idx] == None:\n",
    "                    cur.nexts[idx] = node()\n",
    "                cur = cur.nexts[idx]\n",
    "                if cur.isEnd and i < len(s) - 1 and s[i + 1] == '/':\n",
    "                    # print(i)\n",
    "                    return False\n",
    "            cur.isEnd = True\n",
    "            return True\n",
    "\n",
    "        folder.sort(key=lambda x: len(x))\n",
    "        # print(folder)\n",
    "\n",
    "        ans = []\n",
    "        for i, s in enumerate(folder):\n",
    "            if add(s):\n",
    "                ans.append(s)\n",
    "        # print(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        folder.sort(key = lambda x:(x,len(x)))\n",
    "        res = [folder[0]]\n",
    "        for i in range(1,len(folder)):\n",
    "            pre = len(res[-1])\n",
    "            if not (pre < len(folder[i]) and res[-1] == folder[i][:pre] and folder[i][pre] == \"/\"):\n",
    "                res.append(folder[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        dic = defaultdict(dict)\n",
    "        for path in folder:\n",
    "            tmp = dic\n",
    "            flag = True\n",
    "            for c in path.split('/')[1:]:\n",
    "                if c not in tmp:\n",
    "                    tmp[c] = dict()\n",
    "                elif 'is_path' in tmp:\n",
    "                    flag = False\n",
    "                    break\n",
    "                tmp = tmp[c]\n",
    "            if flag:\n",
    "                tmp['is_path'] = path\n",
    "        def helper(tie):\n",
    "            if 'is_path' in tie:\n",
    "                res.append(tie['is_path'])\n",
    "                return\n",
    "            for k in tie:\n",
    "                helper(tie[k])\n",
    "        res = []\n",
    "        helper(dic)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        \n",
    "        dct = dict()\n",
    "        for f in folder:\n",
    "            path = f.split(\"/\")\n",
    "            cur = dct\n",
    "            for w in path:\n",
    "                if w not in cur:\n",
    "                    cur[w] = dict()\n",
    "                cur = cur[w]\n",
    "            cur[\"is_end\"] = 1\n",
    "        \n",
    "        ans = []\n",
    "        def dfs(path, cur):\n",
    "            if \"is_end\" in cur:\n",
    "                ans.append(\"/\".join(path))\n",
    "                return \n",
    "            for w in cur:\n",
    "                dfs(path+[w], cur[w])\n",
    "            return \n",
    "        \n",
    "        dfs([], dct)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        dic = defaultdict(dict)\n",
    "        for path in folder:\n",
    "            path = path.split('/')\n",
    "            tmp = dic\n",
    "            for c in path:\n",
    "                if c not in tmp:\n",
    "                    tmp[c] = dict()\n",
    "                tmp = tmp[c]\n",
    "            tmp['is_path'] = True\n",
    "        def helper(tie):\n",
    "            if 'is_path' in tie:\n",
    "                print(path)\n",
    "                res.append('/'.join(path))\n",
    "                return\n",
    "            for k in tie:\n",
    "                path.append(k)\n",
    "                helper(tie[k])\n",
    "                path.pop()\n",
    "        path = []\n",
    "        res = []\n",
    "        helper(dic)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        dic = defaultdict(dict)\n",
    "        for path in folder:\n",
    "            path_split = path.split('/')\n",
    "            tmp = dic\n",
    "            for c in path_split:\n",
    "                if c not in tmp:\n",
    "                    tmp[c] = dict()\n",
    "                tmp = tmp[c]\n",
    "            tmp['is_path'] = path\n",
    "        def helper(tie):\n",
    "            if 'is_path' in tie:\n",
    "                res.append(tie['is_path'])\n",
    "                return\n",
    "            for k in tie:\n",
    "                helper(tie[k])\n",
    "        res = []\n",
    "        helper(dic)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.finished = False\n",
    "        self.child = dict()\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        def dfs(cur: Trie, txt: str) -> None:\n",
    "            if cur.finished: ret.append(txt)\n",
    "            else:\n",
    "                for c in cur.child:\n",
    "                    dfs(cur.child[c], txt+f\"/{c}\")\n",
    "\n",
    "        root = Trie()\n",
    "        for f in folder:\n",
    "            cur = root\n",
    "            for d in f.split(\"/\")[1:]:\n",
    "                if not d in cur.child: cur.child[d] = Trie()\n",
    "                cur = cur.child[d]\n",
    "            cur.finished = True\n",
    "        \n",
    "        ret = []\n",
    "        dfs(root, \"\")\n",
    "        return ret\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode(object):\n",
    "\n",
    "    def __init__(self) -> None:\n",
    "        super().__init__()\n",
    "        self.childs = dict()\n",
    "        self.is_end = False\n",
    "\n",
    "\n",
    "class Trie(object):\n",
    "\n",
    "    def __init__(self) -> None:\n",
    "        super().__init__()\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, path):\n",
    "        splits = path.strip(\"/\").split(\"/\")\n",
    "        cur = self.root\n",
    "        for it in splits:\n",
    "            if it not in cur.childs:\n",
    "                cur.childs[it] = TrieNode()\n",
    "            cur = cur.childs[it]\n",
    "        cur.is_end = True\n",
    "\n",
    "    def is_has_parent(self, path):\n",
    "        splits = path.strip(\"/\").split(\"/\")\n",
    "        cur = self.root\n",
    "        for it in splits:\n",
    "            if it in cur.childs:\n",
    "                if cur.is_end is True:\n",
    "                    return True\n",
    "                cur = cur.childs[it]\n",
    "            else:\n",
    "                return False\n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        trie = Trie()\n",
    "        for it in folder:\n",
    "            trie.insert(it)\n",
    "        result = list()\n",
    "        for it in folder:\n",
    "            if trie.is_has_parent(it):\n",
    "                continue\n",
    "            result.append(it)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.fid = -1\n",
    "\n",
    "    def insert(self, i, f):\n",
    "        node = self\n",
    "        ps = f.split('/')\n",
    "        for p in ps[1:]:\n",
    "            if p not in node.children:\n",
    "                node.children[p] = Trie()\n",
    "            node = node.children[p]\n",
    "        node.fid = i\n",
    "\n",
    "    def search(self):\n",
    "        def dfs(root):\n",
    "            if root.fid != -1:\n",
    "                ans.append(root.fid)\n",
    "                return\n",
    "            for child in root.children.values():\n",
    "                dfs(child)\n",
    "\n",
    "        ans = []\n",
    "        dfs(self)\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        trie = Trie()\n",
    "        for i, f in enumerate(folder):\n",
    "            trie.insert(i, f)\n",
    "        return [folder[i] for i in trie.search()]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.fid = -1\n",
    "\n",
    "    def insert(self, i, f):\n",
    "        node = self\n",
    "        ps = f.split('/')\n",
    "        for p in ps[1:]:\n",
    "            if p not in node.children:\n",
    "                node.children[p] = Trie()\n",
    "            node = node.children[p]\n",
    "        node.fid = i\n",
    "\n",
    "    def search(self):\n",
    "        def dfs(root):\n",
    "            if root.fid != -1:\n",
    "                ans.append(root.fid)\n",
    "                return\n",
    "            for child in root.children.values():\n",
    "                dfs(child)\n",
    "\n",
    "        ans = []\n",
    "        dfs(self)\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        trie = Trie()\n",
    "        for i, f in enumerate(folder):\n",
    "            trie.insert(i, f)\n",
    "        return [folder[i] for i in trie.search()]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = dict()\n",
    "        self.ref = -1\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        root = Trie()\n",
    "        for i, path in enumerate(folder):\n",
    "            path = path.split(\"/\")\n",
    "            cur = root\n",
    "            for name in path:\n",
    "                if name not in cur.children:\n",
    "                    cur.children[name] = Trie()\n",
    "                cur = cur.children[name]\n",
    "            cur.ref = i\n",
    "        \n",
    "        ans = list()\n",
    "\n",
    "        def dfs(cur: Trie):\n",
    "            if cur.ref != -1:\n",
    "                ans.append(folder[cur.ref])\n",
    "                return\n",
    "            for child in cur.children.values():\n",
    "                dfs(child)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = dict()\n",
    "        self.ref = -1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        root = Trie()\n",
    "        for i, path in enumerate(folder):\n",
    "            path = path.split('/')\n",
    "            cur = root\n",
    "            for name in path:\n",
    "                if name not in cur.children:\n",
    "                    cur.children[name] = Trie()\n",
    "                cur = cur.children[name]\n",
    "            cur.ref = i\n",
    "        \n",
    "        ans = list()\n",
    "\n",
    "        def dfs(cur: Trie):\n",
    "            if cur.ref != -1:\n",
    "                ans.append(folder[cur.ref])\n",
    "                return\n",
    "            \n",
    "            for child in cur.children.values():\n",
    "                dfs(child)\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = dict()\n",
    "        self.ref = -1\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        root = Trie()\n",
    "        for i, f in enumerate(folder):\n",
    "            fs = f.split('/')\n",
    "            cur = root\n",
    "            for x in fs:\n",
    "                if x not in cur.children:\n",
    "                    cur.children[x] = Trie()\n",
    "                cur = cur.children[x]\n",
    "            cur.ref = i\n",
    "        res = []            \n",
    "        def dfs(root):\n",
    "            if root.ref != -1:\n",
    "                res.append(folder[root.ref])\n",
    "                return\n",
    "            for ch in root.children.values():\n",
    "                dfs(ch)\n",
    "        dfs(root)\n",
    "        return res                       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = dict()\n",
    "        self.ref = -1\n",
    "\n",
    "class Solution:\n",
    "    def removeSubfolders(self, folder: List[str]) -> List[str]:\n",
    "        root = Trie()\n",
    "        for i, path in enumerate(folder):\n",
    "            path = path.split(\"/\")\n",
    "            cur = root\n",
    "            for name in path:\n",
    "                if name not in cur.children:\n",
    "                    cur.children[name] = Trie()\n",
    "                cur = cur.children[name]\n",
    "            cur.ref = i\n",
    "        \n",
    "        ans = list()\n",
    "\n",
    "        def dfs(cur: Trie):\n",
    "            if cur.ref != -1:\n",
    "                ans.append(folder[cur.ref])\n",
    "                return\n",
    "            for child in cur.children.values():\n",
    "                dfs(child)\n",
    "\n",
    "        dfs(root)\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
